
class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}
public class ReverseLink {

//    迭代
    public Node reverseList(Node head) {
        if (head == null) {
            return null;
        }
        Node pre = null;
        Node cur = head;
        Node last = null;
        while (cur != null) {
            last = cur.next;
            cur.next = pre;
            pre = cur;
            cur = last;
        }
        return pre;
    }


//    递归
    public Node reverseList2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node new_head = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return new_head;
    }
}
